The present invention relates to computer compilers, and more particularly to splitting computer functions for more efficient operation.
Early in the history of programming, people realized that they needed to define a standard way of calling functions. This was done so that it would be possible to call a function for which you do not have definition. For example, it could be calling a function defined in a different object file or in a shared library. This convention is called the application binary interface (ABI). The ABI is needed, but it causes there to be a number of instructions to be executed every time a function is called that does not relate to the main task of the program being run. These instructions are the call overhead. In many modern programs, the call overhead is a significant portion of the run time.
A compiler is a computer program (or set of programs) that transforms source code written in a programming language (the source language) into another computer language (the target language, often having a binary form known as object code). The most common reason for converting source code is to create an executable program. The name “compiler” is primarily used for programs that translate source code from a high-level programming language to a lower level language (e.g., assembly language or machine code).
Compliers often begin to analyze a program by building a Control Flow Graph (CFG). A CFG is a visual technique that uses a directed graph possessing nodes, such as basic blocks and regions, where a basic block would be a collection of instructions and a region a collection of basic blocks. Basic Blocks are a portion of the code within a program with only one entry point and only one exit point. This makes a basic block highly amenable to analysis. Compilers usually decompose programs into their basic blocks as a first step in the analysis process. Typically, basic blocks form the vertices or nodes in a control flow graph.
In control flow graphs, a node “d” dominates a node “n” if every path from the entry node to n must go through d. A node d strictly dominates a node n if d dominates n and d does not equal n. The immediate dominator of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. A dominator tree is a tree where each node's children are those nodes it immediately dominates. Because the immediate dominator is unique, it is a tree. The entry node is the root of the tree.
In control flow graphs, a region is said to be strongly connected if every vertex is reachable from every other vertex.